1. Field of the Invention
The present invention relates to a maximum likelihood detector, error correction circuit and medium storage device, and more particularly to a maximum likelihood detector, error correction circuit and medium storage device for correcting the error of data to which ECC code is attached.
2. Description of the Related Art
In the field of recording/reproducing devices, such as magnetic disk devices, and communication systems, Reed Solomon codes are used as the error correction codes (ECC). In order to improve reliability of data reproduction when reproducing data from low quality transmission signals and recording/reproducing signals, data decoding technology using maximum likelihood sequence detection and error correction technology using error correction codes (ECC) are widely used.
A bit string, which is output from the maximum likelihood detector, has an incorrect value in several bits because of the influence of medium noise and circuit noise. An ECC performs error correction for a bit string which has an error, and outputs a bit string of which error is corrected. In the case of a magnetic disk device, for example, retry is required if an ECC fails in correction, but retry must be avoided as much as possible. Therefore it has been proposed that ECC receives some candidate strings from the maximum likelihood detector, and sequentially tries to decode the candidate strings (Japanese Patent Application Laid-Open No. H11-330985, for example).
FIG. 17 is a block diagram depicting a conventional error correction circuit using the maximum likelihood sequence, and FIG. 18 to FIG. 20 are diagrams depicting the operation thereof.
As FIG. 17 shows, a maximum likelihood detector 20 creates a plurality of candidate data strings from the input signals according to a maximum likelihood sequence. A data storage section 31 stores the created plurality of candidate data strings. An ECC decoder 22 has a syndrome calculation section 41, error locator polynomial calculation section 42, chien search execution section 43 and error value calculation section 44.
The syndrome calculation section 41 calculates a syndrome calculation expression (described in FIG. 18 or later) of the data string which is input to the ECC decoder 22. The error locator polynomial calculation section 42 calculates an error locator polynomial from the syndrome polynomial (described in FIG. 18 or later). For a calculation algorithm of the error locator polynomial, a Euclidian method or Berlekamp Massey method is used, for example (see E. R. Berlekamp, “Algebraic Coding Theory”, McGraw-Hill Book Co., pp. 176-199 and pp. 218-240, New York, 1968, and J. L. Massey, “Shift-register Synthesis and BCH Decoding”, IEEE Transactions on Information Theory, Vol. IT-15, pp. 122-127, 1969, for example).
The chien search execution section 43 executes chien search using the above mentioned error locator polynomial, and determines a position on the data string where error exists (error position). The error value calculation section 44 corrects the erred value on the error position to a correct value. Then the decoding judgment section 32 checks the validity of the data string after correction, which is output from the error value calculation section 44, and if not valid, the decoding judgment section 32 judges this as a correction failure, and instructs the data storage section 31 to output the next decoding candidate data string.
Error correction based on the Reed Solomon codes will now be described more specifically with reference to FIG. 18 to FIG. 20. As FIG. 18 shows, the Reed Solomon codes with the number of error corrections ‘t’ is generated by a generating polynomial of degree 2t. If the Galois field used for encoding is GF (third power of 2), and if the number of error corrections ‘t’ is “1”, then the generating polynomial of a Reed Solomon code is expressed by the following Expression (1), for example, using primitive element α.
                    [                  Expression          ⁢                                          ⁢          1                ]                                                                                                                G                ⁡                                  (                  x                  )                                            =                                                (                                      x                    -                    1                                    )                                ⁢                                  (                                      x                    -                    α                                    )                                                                                                        =                                                x                  2                                +                                                      α                    3                                    ⁢                  x                                +                α                                                                        (        1        )            
In this case, starting with α0=1, three bits of a bit string is handled as one symbol, and a parity string with symbol 2t (=2) is added to an information string in ECC encoding. For example, in order to encode an information string in FIG. 18, “001”, “110” and “101” correspond to 1, the fifth power of α and the fourth power of α in the Galois field notation. The j-th symbol is a coefficient of the term xj in the polynomial of a transmission word string. Therefore the bit string (information string) indicates a polynomial x4+α5x3+α4x2.
As FIG. 19 shows, in ECC encoding, the polynomial representing the bit string is divided by the generating polynomial in Expression (1), and the parity string representing the acquired remainder polynomial α4x+α4 is added to the bit string. In this remainder polynomial, the coefficients of the terms of degree 1 and degree 0 of x are both α4, so a parity string shown in FIG. 18 is added, and a transmission word string consisting of 5 symbols is generated.
If this transmission word string is recorded in a magnetic disk and read, for example, a receive word string, including an error as shown in FIG. 20, could be input to the ECC decoder 22. This receive word string is given by the following Expression (2).[Expression 2]Y(x)=αx4+α5x3+α4x2+α4x+α4  (2)
For this receive word string in FIG. 20, the syndrome calculation section 41 calculates the syndrome polynomial by the following Expression (3).[Expression 3]S(x)=s1+s2x s1=Y(1)s2=Y(α)  (3)
In Expression (3), the syndrome si (i=1, 2, . . . , 2t) is a value obtained by substituting the i-th root of the generating polynomial G (x) in Expression (1) for the receive word polynomial Y (x), and the syndrome polynomial S (x) is a polynomial in which the syndrome si is a coefficient of the term xi-1. If an error is not included in the receive word string, all si becomes “0”.
Then the error locator polynomial calculation section 42 calculates the error locator polynomial C (x) of the following Expression (4) using the syndrome polynomial S (x).[Expression 4]C(x)=1+α−4x  (4)
Then the chien search execution section 43 calculates the value of C (αj) (j=0, 1, 2, 3, 4) using the error locator polynomial C (x) in Expression (4), and outputs position j where C (αj)=0 as the error position. In the case of the example in FIG. 20, C (α4)=1+α−4·α4=0, so the error existing in the fourth symbol can be detected.
Then the error value calculation section 44 calculates a correct value of the fourth symbol by a predetermined algorithm using the syndrome polynomial S (x) of Expression (3) and the error locator polynomial C (x) of Expression (4), and corrects the bit string. In this example, a correct value “1” is determined, and the fourth symbol in the receive word string shown in FIG. 20 is corrected from α to “1”.
In the case of a magnetic disk device, for example, a Reed Solomon code, of which number of error corrections t=20, is used, and in ECC error encoding, one symbol consists of 10 bits, and a parity string with 40 symbols is inserted in front of one sector of the bit string (4096 bits=410 symbols). In this case, the syndrome polynomial S (x) and the error locator polynomial C (x) are given by the following Expressions (5) and (6), for example.[Expression 5]S(x)=s1+s2x+ . . . +s40x39  (5)[Expression 6]C(x)=1+x+α2x2+ . . . +α35x8  (6)
An actual receive word string is long, so the degree of the receive word polynomial Y (x) becomes large. In prior art, it is necessary to receive a plurality of candidate data strings and to sequentially try to decode candidate data strings by ECC. If the creation of a candidate data string of a maximum likelihood detector is inappropriate, ECC decoding could fail for all candidate data strings, and correction performance cannot be improved.
If a maximum likelihood detector is provided for all the candidates, the sequence of the candidates must be sorted and transferred to the ECC decoder in the sequence of lower likelihood, so the calculation volume for creating candidate data strings increases, and the circuit scale increases.